{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第3章 从低延迟应用的角度探索C++概念"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 女追男，隔层纱；男追女，隔层妈。\n",
    "\n",
    "在本章中，我们假设读者对C++编程概念、特性等有中级水平的理解。我们将讨论如何用C++进行低延迟应用开发，接着探讨在开发低延迟应用时应特别避免使用哪些C++特性，然后讨论使C++非常适合低延迟应用的关键特性，以及在本书后续内容中我们将如何使用这些特性。最后，我们将讨论如何最大限度地发挥编译器的优化作用，以及哪些C++编译器标志对低延迟应用很重要。\n",
    "\n",
    "在本章中，我们将涵盖以下主题：\n",
    "\n",
    "- 用C++进行低延迟应用开发的方法\n",
    "- 避免陷阱并利用C++特性最小化应用延迟\n",
    "- 最大化C++编译器优化参数\n",
    "\n",
    "让我们在下一节开始讨论用C++进行低延迟应用开发的高层次思路。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 技术要求\n",
    "\n",
    "本章的源代码在仓库的`Chapter3`目录中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 用C++进行低延迟应用开发的方法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在本节中，我们将讨论在尝试用C++构建低延迟应用时，需要牢记的高层次思路。总的来说，这些思路包括了解应用运行的架构、对延迟敏感的应用用例、所选的编程语言（在本书中是C++）、如何使用开发工具（编译器、链接器等），以及在实践中如何衡量应用性能，以便确定首先优化应用的哪些部分。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 先确保代码正确，再进行优化\n",
    "\n",
    "对于低延迟应用，在不同用例和场景下应用的正确行为，以及对边界情况的稳健处理仍然是首要关注点。一个运行速度很快但不能满足需求的应用是没有用的，所以开发低延迟应用的最佳方法是首先确保代码正确，而不是追求速度。只有在应用能正确运行后，才应将重点转移到优化应用的关键部分，同时还要保证正确性。这能确保开发者把时间花在优化正确的部分上，因为通常会发现，我们对哪些部分对性能至关重要的直觉与实际情况并不相符。优化代码所需的时间可能比确保代码正确所需的时间长得多，所以先优化最重要的部分很重要。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 设计最优的数据结构和算法\n",
    "\n",
    "设计适合应用用例的自定义数据结构是构建低延迟应用的重要部分。对于应用关键部分中使用的每个数据结构，都需要从可扩展性、稳健性以及在实际用例和遇到的数据下的性能等方面进行深入思考。理解为什么这里提到 “实际情况” 很重要，因为即使不同的数据结构具有相同的输出或行为，它们在不同的用例和输入数据下的表现也会有所不同。在讨论用不同数据结构和算法解决同一问题的示例之前，让我们快速回顾一下**大O表示法**。大O表示法用于描述执行特定任务的渐近最坏时间复杂度。这里的 “渐近” 是指我们讨论的是在理论上无限（实际上是非常大）数量的数据点上衡量性能的情况。渐近性能消除了所有常数项，仅将性能描述为输入数据元素数量的函数。\n",
    "\n",
    "一个用不同数据结构解决同一问题的简单例子是通过键值在容器中查找条目。我们既可以使用期望平均时间复杂度为O(1)的哈希表实现，也可以使用复杂度为O(n)的数组（其中n是容器中的元素数量）来解决这个问题。\n",
    "从理论上看，哈希表显然是更好的选择，但其他因素，如元素数量、对键应用哈希函数的复杂度等，可能会改变哪种数据结构更合适。在这种情况下，对于少量元素，由于缓存性能更好，数组解决方案更快；而对于大量元素，哈希表解决方案则更优。这里，我们选择了一个理论上不是最优的算法，因为由于缓存性能，该算法底层的数据结构在实际中表现更好。\n",
    "\n",
    "另一个略有不同的例子是，对于某些数学函数（比如三角函数），使用查找表而不是重新计算值。虽然从预计算的查找表中查找结果通常比进行计算要快，但并非总是如此。例如，如果查找表非常大，那么计算浮点表达式的成本可能低于缓存未命中并从主内存中读取查找表值的成本。如果从主内存访问查找表会导致大量缓存污染，从而降低应用程序其他部分的性能，那么整个应用程序的性能可能也会受到影响。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 关注处理器\n",
    "\n",
    "现代处理器在架构和功能方面有很多细节，低延迟应用开发者，尤其是C++开发者，应该了解这些内容，因为C++允许进行底层控制。现代处理器具有多个核心、更大且专门的寄存器组、流水线指令处理（在执行当前指令时预取下一条所需指令）、指令级并行、分支预测、扩展指令集以实现更快和专门的处理等等。应用开发者对其应用运行的处理器的这些方面了解得越多，就越能避免编写次优代码和做出不理想的编译选择，从而确保编译后的机器代码针对目标架构是最优的。至少，开发者应该使用编译器优化标志指示编译器为特定目标架构输出代码，我们将在本章后面讨论这个话题。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 理解缓存和内存访问成本\n",
    "\n",
    "通常，在低延迟应用开发中，从减少工作量或执行指令数量的角度出发，人们会在数据结构和算法的设计与开发上投入大量精力。虽然这是正确的方法，但在本节中，我们想指出，考虑缓存和内存访问同样重要。\n",
    "\n",
    "在上一小节 “设计最优的数据结构和算法” 中，我们看到理论上不是最优的数据结构和算法在实际中往往比理论上最优的表现更好。这背后的一个重要原因是，最优解决方案的缓存和内存访问成本较高，超过了处理器执行较少指令所节省的时间。换个角度想，即使从算法步骤数量的角度来看工作量较少，但在现代处理器、缓存和内存访问架构下，实际完成任务所需的时间却更长。\n",
    "\n",
    "让我们快速回顾一下现代计算机架构中的内存层次结构。请注意，这里回顾的详细内容可以在我们的另一本书《Developing High-Frequency Trading Systems》中找到。关键要点是，**内存层次结构**的工作方式是，如果CPU在寄存器中找不到下一个所需的数据或指令，它会去L0缓存中查找，如果在L0缓存中也找不到，就会按顺序去L1缓存、L2缓存及其他缓存查找，最后去主内存查找。注意，存储设备的访问速度从快到慢，同时存储空间从小到大。有效的低延迟和缓存友好型应用开发的关键在于编写代码时要考虑代码和数据访问模式，尽可能提高在最快存储设备中找到数据的可能性。这依赖于最大化时间局部性和空间局部性的概念。这两个术语分别意味着最近访问的数据很可能在缓存中，以及与我们刚刚访问的数据相邻的数据也很可能在缓存中。\n",
    "下面的图表直观展示了寄存器、缓存和内存库，并提供了一些从CPU访问的时间数据。请注意，访问时间会因硬件不同以及技术的不断改进而有很大差异。这里的关键要点是，从CPU寄存器到缓存库再到主内存，访问时间会显著增加。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"./images/3.1.png\" alt=\"3.1\" style=\"zoom:50%;\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 图3.1 现代计算机架构中的内存层次结构\n",
    "\n",
    "我建议你仔细考虑算法在局部以及整个应用全局的缓存和内存访问模式，确保你的源代码优化了缓存和内存访问模式，这将提升整个应用的性能。如果你有一个函数在调用时执行得很快，但会导致大量缓存污染，那么这将降低整个应用的性能，因为其他组件会因缓存未命中而产生额外的开销。在这种情况下，即使我们可能使这个函数在局部达到了最优性能，但从整个应用的角度来看，我们并没有实现最优性能。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 理解C++特性的底层原理\n",
    "\n",
    "在开发低延迟应用时，开发者非常清楚高级语言抽象在底层是如何工作的，这一点非常重要。对于对延迟不敏感的应用来说，这可能没那么重要，因为只要应用的行为符合开发者的预期，源代码是如何实现这一点的底层细节就无关紧要。\n",
    "\n",
    "对于用C++开发的低延迟应用，开发者对程序如何编译成机器代码了解得越多，就越能更好地利用编程语言实现低延迟性能。C++提供的许多高级抽象提高了开发的便捷性、速度、稳健性、安全性、可维护性以及软件设计的优雅性等，但并非所有这些抽象在低延迟应用中都是最优的。\n",
    "\n",
    "*许多C++特性，如动态多态、动态内存分配和异常处理，对于大多数应用来说都是很好的补充。然而，在低延迟应用中，最好避免使用这些特性，或者谨慎使用，或者以特定方式使用，因为它们会带来较大的开销。*\n",
    "\n",
    "相反，传统编程实践建议开发者为了可重用性将所有内容分解为许多非常小的函数；在适用的情况下使用递归函数；使用面向对象编程（Object-Oriented Programming，OOP）原则，如继承和虚函数；总是使用智能指针而不是原始指针等等。这些原则对大多数应用来说是合理的，但对于低延迟应用，需要仔细评估和使用，因为它们可能会带来不可忽视的开销和延迟。\n",
    "\n",
    "这里的关键要点是，低延迟应用开发者要非常了解这些C++特性中的每一个，理解它们在机器代码中的实现方式、对硬件资源的影响以及在实际中的性能表现。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 利用C++编译器\n",
    "\n",
    "现代C++编译器是一款非常出色的软件。构建这些编译器投入了大量精力，以确保其稳健性和正确性。在对开发者的高级源代码进行转换和优化方面，编译器也做了很多努力，使其变得非常智能。对于希望尽可能提高应用性能的低延迟应用开发者来说，了解编译器如何将开发者的代码转换为机器指令、如何尝试优化代码以及在哪些情况下优化失败非常重要。我们将在本章中广泛讨论编译器的工作原理和优化机会，以便在优化最终应用的表示（机器代码可执行文件）时，学会与编译器合作，而不是与它对抗。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 测量和提升性能\n",
    "\n",
    "我们提到，理想的应用开发过程是先确保应用正确运行，然后再考虑优化。我们还提到，开发者在识别性能瓶颈时，直觉往往是错误的。\n",
    "\n",
    "最后，我们还提到优化应用的任务可能比开发出正确运行的应用要花费长得多的时间。因此，建议开发者在开始优化之前，尝试在实际约束和输入下运行应用以检查性能。以不同形式在应用中添加性能监测工具来测量性能并找到瓶颈，从而了解并确定优化的优先级，这一点很重要。这也是一个重要步骤，因为随着应用的发展，测量和提升性能仍然是工作流程的一部分，也就是说，测量和提升性能是应用发展的一部分。在本书的最后一节 “分析和提升性能” 中，我们将通过一个实际案例研究来更好地理解这个概念。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 避免陷阱并利用C++特性最小化应用延迟\n",
    "\n",
    "在本节中，我们将探讨不同的C++特性，若正确使用这些特性，可最小化应用延迟。在本小节中，我们还将讨论以优化应用性能的方式使用这些特性的细节。现在，让我们开始学习如何正确使用这些特性来最大化应用性能，避免陷阱以最小化延迟。请注意，本章所有代码片段都在本书GitHub仓库的[`Chapter3`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/tree/main/Chapter3)目录中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 选择存储方式\n",
    "\n",
    "在函数内部创建的局部变量默认存储在栈上，栈内存还用于存储函数返回值。假设没有创建大型对象，相同范围的栈存储空间会被大量重复使用，由于引用的局部性，这会带来良好的缓存性能。\n",
    "\n",
    "寄存器变量离处理器最近，是最快的存储形式。但它们的数量极为有限，编译器会尝试将其用于使用频率最高的局部变量，这也是优先使用局部变量的另一个原因。\n",
    "\n",
    "从缓存性能的角度来看，静态变量效率较低，因为该内存不能被其他变量复用，而且对静态变量的访问可能只占所有内存访问的一小部分。因此，最好*避免使用静态变量以及全局变量，因为全局变量的缓存性能同样低效*。\n",
    "\n",
    "`volatile`关键字指示编译器禁用许多依赖于变量值在编译器不知情时不会改变这一假设的优化。只有在多线程用例中才应谨慎使用它，因为它会阻止诸如将变量存储在寄存器中以及每次变量值更改时强制将其从缓存刷新到主内存等优化。\n",
    "\n",
    "> - **`volatile` 的作用**：告诉编译器该变量随时可能被外部（如硬件寄存器）修改，因此不要对其做寄存器缓存或相关优化。但是它并不提供同步语义，也不会禁止编译器、CPU 做重排序。\n",
    "> - **多线程可见性与原子性**：在并发场景下，要保证一个标志位在不同线程之间的可见性和原子性（以及可能需要的内存序约束），应该使用 > `std::atomic<bool>`。`std::atomic` 才会确保每个线程看到的值是及时、可预测的，且读写操作具有原子性。\n",
    "\n",
    "动态分配内存的分配和释放效率较低，并且根据使用方式的不同，可能会出现缓存性能不佳的情况。本节后面的“动态分配内存”小节将进一步讨论动态分配内存的低效问题。\n",
    "\n",
    "利用存储选择优化的C++优化技术示例是**小字符串优化（Small String Optimization，SSO）**。如果短字符串的长度小于特定大小（通常为32个字符），SSO会尝试使用局部存储，而不是默认使用动态分配内存来存储字符串内容。\n",
    "\n",
    "总之，在程序执行过程中，尤其是在关键部分，你应该仔细考虑数据的存储位置。我们应尽量使用寄存器和局部变量，优化缓存性能。仅在必要时或不影响关键路径性能的情况下，才使用`volatile`、静态、全局和动态内存。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 选择数据类型\n",
    "\n",
    "*只要最大寄存器的大小大于整数的大小，C++中的整数运算通常会非常快。*小于或大于寄存器大小的整数有时会比普通整数稍慢。这是因为处理器必须为单个变量使用多个寄存器，并且对于大整数还需应用一些进位逻辑。相反，处理小于寄存器大小的整数时，通常是使用普通寄存器，将高位清零，仅使用低位，并且可能会调用类型转换操作。请注意，额外开销非常小，一般无需担心。有符号整数和无符号整数的运算速度相同，但在某些情况下，无符号整数比有符号整数更快。只有在处理器需要检查和调整符号位时，有符号整数运算才会稍慢一点。同样，即使存在这种额外开销，它也极小，在大多数情况下不一定需要担心。我们来看看不同运算的成本——加法、减法、比较、位运算等通常只需一个时钟周期。乘法运算耗时较长，除法运算耗时最长。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 使用类型转换操作\n",
    "\n",
    "*有符号整数和无符号整数之间的转换是无开销的。*将较小尺寸的整数转换为较大尺寸的整数可能需要一个时钟周期，但有时可以优化为无开销。将较大尺寸的整数转换为较小尺寸的整数则没有额外成本。\n",
    "\n",
    "*浮点数（`float`）、双精度浮点数（`double`）和长双精度浮点数（`long double`）之间的转换通常是无开销的*，只有在极少数情况下除外。将有符号和无符号整数转换为浮点数或双精度浮点数需要几个时钟周期。无符号整数的转换可能比有符号整数耗时更长。\n",
    "\n",
    "将浮点数值转换为整数的成本可能极高——需要50到100个时钟周期甚至更多。如果这些转换位于关键路径上，低延迟应用开发者通常会尝试通过启用特殊指令集、尽可能避免或重构这些转换，或者使用特殊的汇编语言舍入实现等方式，来提高转换效率。\n",
    "\n",
    "*将一种类型的指针转换为另一种类型的指针是完全无开销的*；但转换是否安全则由开发者负责。将指向一个对象的指针类型转换为指向不同对象的指针，这违反了严格别名规则（strict aliasing rule），该规则指出不同类型的两个指针不能指向同一内存位置。这实际上意味着，即使两个指针指向相同的地址，编译器也可能不会使用相同的寄存器来存储它们。请记住，CPU寄存器是处理器可用的最快存储形式，但存储容量极其有限。因此，当使用额外的寄存器来存储相同的变量时，这是对寄存器的低效使用，会对整体性能产生负面影响。\n",
    "\n",
    "这里给出一个将指针类型转换为不同对象的示例。该示例将`double *`转换为`uint64_t *`，并使用`uint64_t`指针修改符号位。这只不过是实现`x = -std::abs(x)`的一种复杂但更高效的方法，但它展示了这种做法是如何违反严格别名规则的（代码位于GitHub上本书的`Chapter3`目录下的[`strict_alias.cpp`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/strict_alias.cpp)文件中）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "orig_x:100.00 x:-100.00 &x:0x7fff011b2ce0 &x_as_ui:0x7fff011b2ce0\n"
     ]
    }
   ],
   "source": [
    "// https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/strict_alias.cpp\n",
    "\n",
    "#include <cstdio>\n",
    "#include <cstdint>\n",
    "\n",
    "{\n",
    "  double x = 100;\n",
    "  const auto orig_x = x;\n",
    "\n",
    "  auto x_as_ui = (uint64_t *) (&x);\n",
    "  *x_as_ui |= 0x8000000000000000;\n",
    "\n",
    "  printf(\"orig_x:%0.2f x:%0.2f &x:%p &x_as_ui:%p\\n\", orig_x, x, &x, x_as_ui);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用现代C++的类型转换操作，`const_cast`、`static_cast`和`reinterpret_cast`在使用时不会产生任何额外开销。然而，对于`dynamic_cast`，它将某个类的对象转换为不同类的对象，在运行时可能成本较高。`dynamic_cast`使用运行时类型信息（Run-Time Type Information，RTTI）检查转换是否有效，这一过程较慢，并且如果转换无效可能会抛出异常——这使得它更安全，但会增加延迟。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 优化数值运算\n",
    "\n",
    "通常，双精度计算所需的时间与单精度运算大致相同。一般来说，*对于整数和浮点值，加法运算很快，乘法运算比加法稍贵，而除法运算比乘法贵得多*。整数乘法大约需要5个时钟周期，浮点乘法大约需要8个时钟周期。大多数处理器上，整数加法只需一个时钟周期，浮点加法大约需要2 - 5个时钟周期。浮点除法和整数除法所需的时间大致相同，大约为20 - 80个时钟周期，具体取决于处理器以及它是否具有特殊的浮点运算功能。\n",
    "\n",
    "编译器会尽可能重写和简化表达式，优先使用更快的运算，例如将除法重写为乘以倒数。对2的幂次方进行乘法和除法运算要快得多，因为编译器会将其重写为位移动操作，而位移动操作要快得多。编译器使用这种优化时会有额外开销，因为它必须处理符号和舍入误差。显然，这仅适用于表达式中涉及在编译时可确定为2的幂次方的值的情况。例如，在处理多维数组时，编译器会尽可能将乘法转换为位移动操作。\n",
    "\n",
    "*应避免在同一表达式中混合单精度和双精度运算，以及涉及浮点和整数值的表达式，因为它们会隐式强制类型转换*。我们之前了解到，类型转换并不总是无开销的，所以这些表达式的计算时间可能比我们预期的更长。例如，在表达式中混合单精度和双精度值时，单精度值必须首先转换为双精度值，这在计算表达式之前可能会消耗几个时钟周期。同样，在表达式中混合整数和浮点值时，要么将浮点值转换为整数，要么将整数转换为浮点值，这会在最终计算时间上增加几个时钟周期。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 优化布尔和位运算\n",
    "\n",
    "布尔运算，如逻辑与（`&&`）和逻辑或（`||`），其求值规则如下：对于`&&`，如果第一个操作数为`false`，则不会计算第二个操作数；对于`||`，如果第一个操作数为`true`，则不会计算第二个操作数。一种简单的优化技巧是，对于`&&`，按照操作数被求值为`true`的概率从低到高的顺序排列；对于`||`，按照操作数为`true`的概率从高到低的顺序排列是最佳选择。这种技术称为**短路布尔运算（short - circuiting the boolean operations）**，它不仅减少了这些操作数的求值次数，还改善了分支预测。但如果操作数的顺序对程序很重要，就不能使用这种技术。例如，对于`&&`布尔运算，如果第一个操作数为`false`，我们要求不计算第二个操作数；或者对于`||`布尔运算，如果第一个操作数为`true`，第二个操作数不应被计算等等。\n",
    "\n",
    "使用布尔变量的另一个要点是理解它们的存储方式。布尔变量存储为8位，而不是我们根据使用方式可能直观认为的1位。这意味着涉及布尔值的操作在实现时，必须将除0以外的任何8位值都视为1，这就导致在实现中会出现与0进行比较的分支。<br/>例如，`c = a && b;`表达式的实现如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "if(a != 0) {\n",
    "    if(b != 0) {\n",
    "        c = true;\n",
    "    } else {\n",
    "        c = false;\n",
    "    }\n",
    "} else {\n",
    "    c = false;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果能保证`a`和`b`的值只能是0或1，那么`c = a && b;`就可以简单地写成`c = a & b;`，这非常快，并且避免了分支和与分支相关的开销。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "位运算还可以通过将整数的每一位视为单个布尔变量，然后用位掩码操作重写涉及多个*布尔值比较的表达式*，从而加快其他布尔表达式的运算速度。<br/>例如，有这样一个表达式，其中`market_state`是`uint64_t`类型，`PreOpen`、`Opening`和`Trading`是反映不同市场状态的枚举值："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "if(market_state == PreOpen ||\n",
    "   market_state == Opening ||\n",
    "   market_state == Trading) {\n",
    "    // do something...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "它可以重写为："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "if(market_state & (PreOpen | Opening | Trading)) {\n",
    "    // do something...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果选择的枚举值使得`market_state`变量中的每一位代表一个`true`或`false`状态，一种选择是将`PreOpen`、`Opening`和`Trading`枚举值分别设置为`0x001`、`0x010`和`0x100`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 初始化、销毁、复制和移动对象\n",
    "\n",
    "开发者自定义类的构造函数和析构函数应尽可能简洁高效，因为它们可能在开发者未预料的情况下被调用。保持这些方法简单小巧，也能让编译器将其内联，从而提高性能。复制构造函数和移动构造函数同样如此，应保持简单，并且尽可能优先使用移动构造函数而非复制构造函数。在许多需要高度优化的场景中，开发者可以删除默认构造函数和复制构造函数，以确保不会对对象进行不必要或意外的复制。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 使用引用和指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C++的许多特性都是围绕通过`this`指针隐式访问类成员构建的，所以无论开发者是否显式操作，通过引用和指针进行访问都非常频繁。通过指针和引用访问对象，在大多数情况下与直接访问对象的效率相当。这是因为大多数现代处理器都支持高效地获取指针值并解引用。使用引用和指针的一大缺点是，它们本身需要占用一个额外的寄存器来存储指针，并且还需要额外的解引用指令来访问指针所指向的变量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "指针运算和整数运算速度相当，只是计算指针之间的差值时需要除以对象的大小，这可能会非常慢。如果对象类型的大小是2的倍数，通常基本类型和经过优化的结构体都是这种情况，那么这不一定是个问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "智能指针（Smart pointers）是现代C++的一项重要特性，它为动态分配的对象提供了安全性、生命周期管理、自动内存管理以及清晰的所有权控制。像`std::unique_ptr`、`std::shared_ptr`和`std::weak_ptr`这样的智能指针采用了C++的资源获取即初始化（RAII，Resource Acquisition is Initialization）范式。由于引用计数的开销，`std::shared_ptr`会带来额外的成本，但一般来说，除非使用大量智能指针，否则它们对整个程序增加的开销很少。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用指针的另一个重要问题是，**指针别名（Pointer Aliasing）**可能会阻碍编译器进行优化。这是因为，虽然对用户来说情况可能很明显，但在编译时，编译器无法保证代码中的两个指针变量永远不会指向同一个内存地址。在那些理论上可能存在指针别名的情况下，一些编译器优化会改变代码的执行结果，因此这些优化会被禁用。<br/>例如，下面这段代码会阻止编译器应用循环不变代码外提优化（loop-invariant code motion）。尽管指针`a[0]`到`a[n - 1]`与`b`之间没有重叠，但这意味着这种优化是有效的，因为`*b`在整个循环中是一个常量，可以只计算一次："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 别名分析限制优化：编译器必须假设 a 和 b 可能指向同一块内存，因此不能把 *b 的读取移出循环，也不能提前矢量化。\n",
    "\n",
    "void func(int* a, int* b, int n) {\n",
    "    for(int i = 0; i < n; ++i) {\n",
    "        a[i] = *b;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在开发者确定不存在依赖指针别名副作用的行为时，有两种方法可以指示编译器假设不存在指针别名。在函数参数或函数上使用`restrict` ，或者使用类似的指定关键字，来指定指针不存在别名。不过这只是一个提示，编译器不能保证这一定会产生效果。另一种方法是指定`-fstrict-aliasing`编译器选项，全局假设不存在指针别名。<br/>下面的代码块展示了对前面的`func()`函数使用`restrict`指定符（可在GitHub上第3章的[`pointer_alias.cpp`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/pointer_alias.cpp)中查看）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// restrict 提示优化：告诉编译器 a 与 b 没有重叠，因而 *b 可被 hoist 到循环外，生成的汇编通常会包含加载一次然后矢量化更新的指令序列，减少访存次数。\n",
    "\n",
    "void func(int * restrict a, int * restrict b, int n) {\n",
    "    for (int i = 0; i < n; ++i) {\n",
    "        a[i] = *b;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd codes && g++ -O3 benchmark_alias.cpp -lbenchmark -lpthread -o bench_alias"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T09:51:05+08:00\n",
      "Running ./bench_alias\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.15, 0.15, 0.12\n",
      "----------------------------------------------------------\n",
      "Benchmark                Time             CPU   Iterations\n",
      "----------------------------------------------------------\n",
      "BM_FuncAlias         67519 ns        67517 ns        11309\n",
      "BM_FuncRestrict      63503 ns        63504 ns        11486\n"
     ]
    }
   ],
   "source": [
    "! cd codes && ./bench_alias"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd codes && g++ -O3 -fstrict-aliasing benchmark_alias.cpp -lbenchmark -lpthread -o bench_alias"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T09:51:19+08:00\n",
      "Running ./bench_alias\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.12, 0.14, 0.12\n",
      "----------------------------------------------------------\n",
      "Benchmark                Time             CPU   Iterations\n",
      "----------------------------------------------------------\n",
      "BM_FuncAlias         65542 ns        65542 ns        11072\n",
      "BM_FuncRestrict      66854 ns        66854 ns        11283\n"
     ]
    }
   ],
   "source": [
    "! cd codes && ./bench_alias"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 优化跳转和分支"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在现代处理器流水线中，指令和数据是分阶段获取和解码的。当遇到分支指令时，处理器会尝试预测将执行哪个分支，并从该分支获取和解码指令。然而，当处理器预测错误时，它需要10个或更多时钟周期才能检测到错误预测。之后，它必须花费一些时钟周期从正确的分支获取指令和数据并进行评估。关键在于，每次分支预测错误都会浪费许多时钟周期。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "让我们来讨论一下C++中一些最常用的跳转和分支形式：\n",
    "\n",
    "- `if-else`分支是讨论分支时最常想到的。如果可能的话，最好避免使用长串的`if-else`条件语句，因为随着条件数量的增加，很难正确预测。减少条件数量，并尝试将它们组织得更易于预测，是优化它们的方法。\n",
    "- `for`和`while`循环也是分支的一种类型，如果循环次数相对较少，通常能被较好地预测。当然，对于嵌套循环和包含难以预测退出条件的循环，情况会变得复杂。\n",
    "- `switch`语句是具有多个跳转目标的分支，因此很难预测。当标签值分布很广时，编译器必须将`switch`语句作为一长串`if-else`分支树来处理。一种对`switch`语句有效的优化技巧是，将`case`标签值设置为逐个递增并按升序排列，因为这样很有可能会被实现为**跳转表（jump tables）**，效率会显著提高。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "只要可能，在源代码中用包含不同输出值的查表操作代替分支是一种很好的优化方法。我们还可以创建一个由跳转条件索引的函数指针表，但要注意，函数指针不一定比分支本身高效得多。\n",
    "\n",
    "如果循环内存在难以预测且可能导致大量分支预测错误的分支，循环展开（Loop unrolling）也有助于减少分支。我们稍后会详细讨论循环展开，现在先简单介绍一下这个概念。循环展开会多次复制循环体，以避免用于判断循环是否继续的检查和分支操作。编译器会尽可能尝试展开循环，但通常开发者自己进行循环展开效果更好。<br/>例如，考虑一个像这样循环次数较少的简单循环（可在GitHub上第3章的[`loop_unroll.cpp`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/loop_unroll.cpp)中查看）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "int a[5]; \n",
    "a[0] = 0;\n",
    "for(int i = 1; i < 5; ++i)\n",
    "    a[i] = a[i - 1] + 1;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "编译器可以将这个循环展开成下面这样的代码。请注意，对于这样一个简单的例子，编译器很可能会使用额外的优化，进一步简化这个循环。但目前我们只关注循环展开的影响："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "int a[5];\n",
    "a[0] = 0;\n",
    "a[1] = a[0] + 1; \n",
    "a[2] = a[1] + 1;\n",
    "a[3] = a[2] + 1; \n",
    "a[4] = a[3] + 1;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用`if constexpr (condition-expression) {}`格式进行编译时分支（Compile-time branching），显然可以将分支的开销转移到编译时，从而有很大帮助，但这要求`condition-expression`能在编译时求值。从技术上讲，这是编译时多态（Compile time Polymorphism）或模板元编程（Template Metaprogramming）范式的一部分，我们将在本节的“使用编译时多态”小节中进一步讨论。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于开发者对预期的用例更了解，所以可以在源代码中为编译器提供分支预测提示。不过总体而言，这些提示不会产生显著影响，因为现代处理器很擅长在经过几次分支迭代后，了解哪些分支最有可能被执行。<br/>对于GNU C++，传统上使用`__builtin_expect`实现如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#define LIKELY_CONDITION(x)    __builtin_expect(!!(x), 1)\n",
    "#define UNLIKELY_CONDITION (x)    __builtin_expect(!!(x), 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在C++ 20中，这些被标准化为`[[likely]]`和`[[unlikely]]`属性。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 高效调用函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "调用函数会带来许多开销，包括获取函数地址并跳转、传递参数和返回结果、设置栈帧、保存和恢复寄存器、异常处理、可能的代码缓存未命中延迟等等。\n",
    "\n",
    "在将代码分解为函数时，为了最大限度地提高性能，通常需要考虑以下几点："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 在创建过多函数前进行思考\n",
    "\n",
    "只有当函数有足够的可复用性时才应该创建。创建函数的标准应该是逻辑程序流和可复用性，而不是代码长度，因为正如我们所见，调用函数并非没有成本，创建过多函数不是一个好主意。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 相关函数分组\n",
    "\n",
    "类成员函数和非类成员函数通常按照创建顺序分配内存地址，所以将那些频繁相互调用或操作相同数据集的性能关键函数分组在一起通常是个好主意。这有助于提高代码和数据缓存的性能。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 链接时优化（Link Time Optimization，LTO）或全程序优化（Whole Program Optimization，WPO）\n",
    "\n",
    "编写对性能要求较高的函数时，如果可能，应将它们放在使用它们的同一模块中。这样做可以解锁许多编译器优化，其中最重要的是能够内联函数调用。\n",
    "\n",
    "使用`static`关键字声明函数，相当于将其放入匿名命名空间，使其在使用它的翻译单元内局部可见。指定`inline`关键字也能达到同样的效果，不过我们将在下一节探讨这一点。\n",
    "\n",
    "为编译器指定`WPO`和`LTO`参数，会指示它将整个代码库视为一个模块，并启用跨模块的编译器优化。如果不启用这些编译器选项，优化只会在同一模块内的函数间进行，而对于通常包含大量源文件和模块的大型代码库来说，这可能不是最优的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 宏、内联函数和模板元编程\n",
    "\n",
    "宏表达式（Macro expressions）是一种预处理指令，在编译开始前就会被展开。这消除了运行时调用函数和从函数返回的开销。不过，宏有一些缺点，比如命名空间冲突、晦涩难懂的编译错误、不必要的条件和表达式求值等等。\n",
    "\n",
    "内联函数（Inlined functions），无论是否属于类的一部分，都与宏类似，但解决了许多与宏相关的问题。内联函数在编译和链接时，会在其使用处展开，消除了函数调用带来的开销。\n",
    "\n",
    "使用模板元编程（Template metaprogramming），可以将大量计算负载从运行时转移到编译时。这涉及使用部分和完全模板特化以及递归循环模板。然而，模板元编程可能会很繁琐，使用、编译和调试都有一定难度，只有在性能提升足以弥补开发难度增加的情况下才适合使用。我们很快就会探讨模板和模板元编程。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 避免使用函数指针\n",
    "\n",
    "通过函数指针调用函数比直接调用函数的开销更大。一方面，如果指针发生变化，编译器就无法预测将调用哪个函数，也无法预取指令和数据。此外，这也会阻碍编译器进行许多优化，因为这些函数在编译时无法内联。\n",
    "\n",
    "`std::function`是现代C++中功能更强大的结构，但只有在必要时才应使用，因为与直接内联函数相比，它存在被误用的可能性，并且会多消耗几个时钟周期的额外开销。`std::bind`是另一个在使用时需要格外小心的结构，同样也应仅在绝对必要时使用。如果必须使用`std::function`，可以尝试看看是否能用lambda表达式替代`std::bind`，因为通常调用lambda表达式会快几个时钟周期。总体而言，在使用`std::function`和 / 或`std::bind`时要谨慎，因为很多开发者会惊讶地发现，这些结构在底层可能会进行虚函数调用并引发动态内存分配。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 通过引用或指针传递函数参数\n",
    "\n",
    "对于基本类型，按值传递参数的效率非常高。对于作为函数参数的复合类型，首选的传递方式是使用常量引用（const references）。常量性（constness）意味着对象不能被修改，这使得编译器可以基于此进行优化，而引用则使编译器有可能直接内联对象本身。如果函数需要修改传递给它的对象，那么显然应使用非常量引用或指针。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 从函数返回简单类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "返回基本类型的函数效率非常高。返回复合类型的效率则低得多，在某些情况下可能会导致创建多个副本，这是非常不理想的，尤其是当这些复合类型很大，并且 / 或者其复制构造函数和赋值运算符的执行速度较慢时。当编译器可以应用**返回值优化（Return Value Optimization，RVO）**时，它可以消除创建的临时副本，直接将结果写入调用者的对象中。返回复合类型的最佳方式是让调用者创建该类型的对象，并使用引用或指针将其传递给函数，以便函数对其进行修改。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "让我们通过一个例子来解释返回值优化（RVO）的原理；假设我们有以下函数定义和函数调用（代码位于GitHub上第3章的[`rvo.cpp`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/rvo.cpp)中）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "struct LargeClass {\n",
    "    int i;\n",
    "    char c;\n",
    "    double d;\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "auto rvoExample(int i, char c, double d) {\n",
    "    return LargeClass{i, c, d};\n",
    "}\n",
    "\n",
    "{\n",
    "    LargeClass lc_obj = rvoExample(10, 'c', 3.14);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用返回值优化（RVO）时，`rvoExample()`函数不会在内部创建一个临时的`LargeClass`对象，然后再将其复制到`main()`函数中的`LargeClass lc_obj`对象中，而是可以直接更新`lc_obj`，从而避免了创建临时对象和复制操作。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 避免递归函数或用循环替代\n",
    "\n",
    "递归函数效率较低，因为它们会反复调用自身，存在额外开销。此外，递归函数可能会在调用栈中深入调用，占用大量栈空间，在最坏的情况下甚至会导致栈溢出（stack overflow）。由于涉及新的内存区域，这会导致大量缓存未命中（cache misses），并且使返回地址的预测变得困难且低效。在这种情况下，用循环替代递归函数会高效得多，因为它避免了递归函数遇到的许多缓存性能问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 使用位域（bitfields）\n",
    "\n",
    "位域是一种结构体，开发者可以在其中控制为每个成员分配的位数。这使得数据尽可能紧凑，对于许多对象来说，能极大地提高缓存性能。位域成员通常也使用位掩码操作（bitmask operations）进行修改，正如我们之前所见，这种操作非常高效。不过，访问位域的成员比访问常规结构体的成员效率更低，所以仔细评估使用位域并提高缓存性能是否值得非常重要。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 使用运行时多态（runtime polymorphism）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当需要在运行时而不是编译时确定要调用的成员函数时，运行时多态是一种很优雅的解决方案。虚函数（Virtual functions）是实现运行时多态的关键，但与非虚函数调用相比，它们存在额外开销。\n",
    "\n",
    "通常，编译器在编译时无法确定将调用虚函数的哪个实现。在运行时，这会导致许多分支预测错误，除非大多数情况下都调用同一个版本的虚函数。编译器有可能通过去虚拟化（devirtualization）在编译时确定调用的虚函数实现，但在很多情况下这是无法做到的。虚函数的主要问题在于，存在虚函数时，编译器无法应用许多编译时优化，其中最重要的就是内联（inlining）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C++中的**继承（Inheritance）**是另一个重要的面向对象编程（OOP）概念，但当继承结构过于复杂时要小心，因为这可能会引入许多不易察觉的低效问题。子类会从父类继承每一个数据成员，因此子类的大小可能会变得相当大，从而导致缓存性能不佳。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一般来说，我们可以考虑使用**组合（Composition**）范式，而不是从多个父类继承。在组合范式中，子类拥有不同父类类型的成员，而不是继承它们。这避免了使用不同父类指针访问子类对象、子类数据成员和方法的偏移量等相关的复杂问题。<br/>下面的示例（位于GitHub上第3章的[`composition.cpp`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/composition.cpp)）展示了两种不同方式构建的`OrderBook`，它主要用于存储`Order`对象的向量（vector）。\n",
    "- 继承模型（如果使用得当）的好处是，它现在继承了`std::vector`提供的所有方法，\n",
    "- 而组合模型则需要自行实现这些方法。在这个示例中，\n",
    "\n",
    "我们通过在`CompositionOrderBook`中实现`size()`方法来演示这一点，该方法调用`std::vector`对象的`size()`方法，而`InheritanceOrderBook`则直接从`std::vector`继承该方法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <cstdio>\n",
    "#include <vector>\n",
    "\n",
    "struct Order {\n",
    "  int id;\n",
    "  double price;\n",
    "};\n",
    "\n",
    "class InheritanceOrderBook : public std::vector<Order> {\n",
    "};\n",
    "\n",
    "class CompositionOrderBook {\n",
    "  std::vector<Order> orders_;\n",
    "\n",
    "public:\n",
    "  auto size() const noexcept {\n",
    "    return orders_.size();\n",
    "  }\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "InheritanceOrderBook::size():0 CompositionOrderBook:0\n"
     ]
    }
   ],
   "source": [
    "{\n",
    "  InheritanceOrderBook i_book;\n",
    "  CompositionOrderBook c_book;\n",
    "\n",
    "  printf(\"InheritanceOrderBook::size():%lu CompositionOrderBook:%lu\\n\", i_book.size(), c_book.size());\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C++的运行时类型识别（RTTI，Runtime Type Information）会为每个类对象添加大量额外的元数据，以便在运行时提取和使用更多信息。这使得这些对象的所有实例效率都变低，对于低延迟应用程序，最好在编译器级别关闭RTTI支持。如果开发者需要为特定的类或对象附加特定的元数据，最好自定义实现，而不是给整个应用程序增加开销。正如我们之前讨论的，`dynamic_cast`通常使用RTTI信息进行类型转换，也应避免使用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 使用编译期多态\n",
    "\n",
    "我们来讨论一下运行时多态的替代方案，即使用模板来实现编译期多态。模板与宏类似，意味着它们在编译前进行展开。正因如此，不仅消除了运行时开销，还为编译器提供了更多优化机会。模板能使编译器生成的机器码超级高效，但代价是增加了源代码的复杂性，同时也会使可执行文件变大。\n",
    "\n",
    "**奇特递归模板模式（Curiously Recurring Template Pattern，CRTP）有助于实现编译期多态**。注意，这里的语法比使用虚函数的运行时多态更复杂，并且使用CRTP时基类和派生类的关系与运行时多态类似，但又略有不同。<br/>这里展示一个将运行时多态转换为编译期多态的简单示例。在这两种情况下，派生类`SpecificRuntimeExample`和`SpecificCRTPExample`都重写了`placeOrder()`方法。本节讨论的代码在本书GitHub仓库中`Chapter3`目录下的[`crtp.cpp`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/crtp.cpp)文件里。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 使用虚函数的运行时多态"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里有一个实现运行时多态的示例，`SpecificRuntimeExample`从`RuntimeExample`派生，并重写了`placeOrder()`方法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <cstdio>\n",
    "\n",
    "class RuntimeExample {\n",
    "public:\n",
    "  virtual void placeOrder() {\n",
    "    printf(\"RuntimeExample::placeOrder()\\n\");\n",
    "  }\n",
    "};\n",
    "\n",
    "class SpecificRuntimeExample : public RuntimeExample {\n",
    "public:\n",
    "  void placeOrder() override {\n",
    "    printf(\"SpecificRuntimeExample::placeOrder()\\n\");\n",
    "  }\n",
    "};\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 使用CRTP的编译期多态"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在我们实现与上一节类似的功能，但不使用运行时多态，而是使用编译期多态。这里，我们使用CRTP模式，`SpecificCRTPExample`特化/实现了`CRTPExample`接口，并通过`actualPlaceOrder()`对`placeOrder()`有不同的实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// CRTP（Curiously Recurring Template Pattern）示例：\n",
    "// 基类模板接收派生类类型作为模板参数。\n",
    "template <typename ActualType>\n",
    "class CRTPExample {\n",
    "public:\n",
    "    void placeOrder() {\n",
    "        // 将当前对象指针转换为派生类指针，\n",
    "        // 这一步使得基类代码能够调用派生类实现的 actualPlaceOrder()。\n",
    "        static_cast<ActualType*>(this)->actualPlaceOrder();\n",
    "    }\n",
    "\n",
    "    void actualPlaceOrder() {\n",
    "        // 如果派生类没有覆盖 actualPlaceOrder()，\n",
    "        // 将使用这个基类中的默认实现。\n",
    "        std::printf(\"CRTPExample::actualPlaceOrder()\\n\");\n",
    "    }\n",
    "};\n",
    "\n",
    "// 派生类将自己作为模板实参传给基类，形成 CRTP 结构。\n",
    "class SpecificCRTPExample : public CRTPExample<SpecificCRTPExample> {\n",
    "public:\n",
    "    void actualPlaceOrder() {\n",
    "        // 覆盖基类的 actualPlaceOrder()，提供具体行为。\n",
    "        std::printf(\"SpecificCRTPExample::actualPlaceOrder()\\n\");\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 在两种情况下调用多态方法\n",
    "\n",
    "最后，在下面的代码片段中，我们展示如何创建`SpecificRuntimeExample`和`SpecificCRTPExample`对象，然后分别使用`placeOrder()`方法调用运行时多态和编译期多态\n",
    "\n",
    "运行这段代码会产生以下输出，第一行使用运行时多态，第二行使用编译期多态："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SpecificRuntimeExample::placeOrder()\n",
      "SpecificCRTPExample::actualPlaceOrder()\n"
     ]
    }
   ],
   "source": [
    "{\n",
    "  RuntimeExample *runtime_example = new SpecificRuntimeExample();\n",
    "  runtime_example->placeOrder();\n",
    "\n",
    "  CRTPExample <SpecificCRTPExample> crtp_example;\n",
    "  crtp_example.placeOrder();\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 使用额外的编译期处理\n",
    "\n",
    "模板元编程（Template metaprogramming）是一个更通用的术语，指编写能生成更多代码的代码。这样做的好处也是将计算从运行时转移到编译期，最大化编译器优化机会，提升运行时性能。用模板元编程几乎可以编写任何东西，但它可能会变得极其复杂，难以理解、维护和调试，导致编译时间极长，并且使二进制文件变得非常大。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 处理异常"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C++异常处理系统旨在检测运行时的意外错误情况，并进行优雅恢复或从该点停止程序。对于低延迟应用，评估异常处理的使用非常重要，因为虽然在这些罕见的错误情况下异常处理会导致最大的延迟，但即使没有抛出异常，也可能存在一些开销。在各种场景下抛出异常时，为了实现优雅恢复的逻辑会有一些记录开销。在嵌套函数中，异常需要一直传播到最顶层的调用函数，并且每个栈帧都需要清理。这被称为**栈展开（stack unwinding）**，要求异常处理程序跟踪在异常发生时向后回溯所需的所有信息。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于低延迟应用，可以使用`throw()`或`noexcept`规范在每个函数中禁用异常，也可以使用编译器标志在整个程序中禁用异常。这使得编译器可以假设部分或所有方法不会抛出异常，因此处理器不必担心保存和跟踪恢复信息。请注意，使用`noexcept`或禁用C++异常处理系统并非没有缺点。一方面，通常情况下，除非抛出异常，否则C++异常处理系统不会增加太多额外开销，所以必须谨慎做出这个决定。另一点是，如果标记为`noexcept`的方法由于某种原因抛出了异常，该异常将无法再沿着栈向上传播，而是会直接终止程序。这意味着部分或完全禁用C++异常处理系统会使处理失败和异常变得更加困难，并且完全成为开发人员的责任。通常这意味着开发人员仍然需要确保不会遇到异常错误情况，或者在其他地方进行处理，但关键在于现在开发人员可以明确控制这一点，并将其从关键的热路径中移除。因此，在开发和测试阶段，通常不会禁用C++异常处理系统，只有在最后的优化步骤中才会考虑移除异常处理。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 访问缓存和内存\n",
    "\n",
    "在讨论C++特性的不同用法时，我们经常提到缓存性能，因为访问主内存的速度比执行CPU指令、访问寄存器或缓存存储所使用的时钟周期要慢得多。在尝试优化缓存和内存访问时，有以下一些要点需要牢记。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 对齐数据"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**对齐的变量**，即被放置在内存地址是其自身大小倍数的位置上的变量，访问效率最高。处理器的**字长（word size）**描述了处理器读取和处理的位数，对于现代处理器来说，通常是32位或64位。这是因为处理器可以在一次读取操作中从内存读取一个不超过字长大小的变量。如果变量在内存中是对齐的，那么处理器就无需做任何额外工作，就能将其读入所需的寄存器进行处理。\n",
    "\n",
    "基于这些原因，处理对齐的变量效率更高，并且编译器会自动处理变量的对齐问题，这包括在类或结构体的成员变量之间添加填充以保持这些变量对齐。当向我们期望创建大量对象的结构体中添加成员变量时，需要仔细考虑添加的额外填充，因为结构体的大小会比预期的更大。这个结构体或类的每个对象实例中的额外空间意味着，如果对象数量很多，它们的缓存性能可能会更差。这里推荐的方法是重新排列结构体的成员，以便在保持成员对齐的同时添加最少的额外填充。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们来看一个示例，以三种不同的方式对结构体中的相同成员进行排序：一种是添加大量额外填充以保持每个变量对齐；另一种是开发人员重新排列成员变量，以尽量减少由于编译器添加填充而造成的空间浪费；最后一种是使用`pack()`编译指示来消除所有填充。这段代码在本书GitHub仓库中[`Chapter3/alignment.cpp`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/alignment.cpp)文件里："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这段代码在我的系统上输出如下内容，展示了相同结构体的三种设计中不同数据成员的偏移量。注意，第一个版本有额外11字节的填充，第二个版本由于重新排序只有额外3字节的填充，最后一个版本没有额外填充："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PoorlyAlignedData c:0 u:2 d:8 i:16 size:24\n",
      "WellAlignedData d:0 u:8 i:10 c:12 size:16\n",
      "PackedData d:0 u:8 i:10 c:12 size:13\n"
     ]
    }
   ],
   "source": [
    "#include <cstdio>\n",
    "#include <cstdint>\n",
    "#include <cstddef>\n",
    "\n",
    "struct PoorlyAlignedData {\n",
    "  char c;\n",
    "  uint16_t u;\n",
    "  double d;\n",
    "  int16_t i;\n",
    "};\n",
    "\n",
    "struct WellAlignedData {\n",
    "  double d;\n",
    "  uint16_t u;\n",
    "  int16_t i;\n",
    "  char c;\n",
    "};\n",
    "\n",
    "#pragma pack(push, 1)\n",
    "struct PackedData {\n",
    "  double d;\n",
    "  uint16_t u;\n",
    "  int16_t i;\n",
    "  char c;\n",
    "};\n",
    "#pragma pack(pop)\n",
    "\n",
    "{\n",
    "  printf(\"PoorlyAlignedData c:%lu u:%lu d:%lu i:%lu size:%lu\\n\",\n",
    "         offsetof(struct PoorlyAlignedData,c), offsetof(struct PoorlyAlignedData,u), offsetof(struct PoorlyAlignedData,d), offsetof(struct PoorlyAlignedData,i), sizeof(PoorlyAlignedData));\n",
    "  printf(\"WellAlignedData d:%lu u:%lu i:%lu c:%lu size:%lu\\n\",\n",
    "         offsetof(struct WellAlignedData,d), offsetof(struct WellAlignedData,u), offsetof(struct WellAlignedData,i), offsetof(struct WellAlignedData,c), sizeof(WellAlignedData));\n",
    "  printf(\"PackedData d:%lu u:%lu i:%lu c:%lu size:%lu\\n\",\n",
    "         offsetof(struct PackedData,d), offsetof(struct PackedData,u), offsetof(struct PackedData,i), offsetof(struct PackedData,c), sizeof(PackedData));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 访问数据\n",
    "\n",
    "对缓存友好的数据访问（读和/或写）是指按顺序或大致按顺序访问数据。如果反向访问数据，效率会比顺序访问低，而随机访问数据时，缓存性能会更差。在访问多维对象数组和/或存储在底层存储结构复杂的容器中的对象时，尤其要考虑这一点。\n",
    "\n",
    "例如，访问数组中的元素比访问链表、树或哈希映射容器中的元素效率要高得多，这是因为数组是连续内存存储，而其他容器是随机内存存储。从算法复杂度的角度来看，在数组中线性搜索的效率比使用哈希映射低，因为数组搜索的理论算法复杂度是O(n)，而哈希映射是O(1)。然而，如果元素数量足够少，那么使用数组仍然能获得更好的性能，这很大程度上是由于缓存性能和算法开销的原因。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 使用大型数据结构\n",
    "\n",
    "例如，在处理大型多维矩阵数据集并进行线性代数运算时，缓存访问性能对运算性能起着决定性作用。通常，矩阵运算的实际算法实现与经典文献中的有所不同，会为了缓存性能对矩阵访问操作重新排序。这里最好的方法是测量不同算法和访问模式的性能，找出在不同矩阵维度、缓存竞争条件等情况下表现最佳的方案。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 变量分组\n",
    "\n",
    "在设计类、方法或非成员函数时，将一起访问的变量分组可以减少缓存未命中次数，从而显著提高缓存性能。我们之前讨论过，相比于全局变量、静态变量和动态分配的内存，优先使用局部变量能带来更好的缓存性能。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 函数分组\n",
    "\n",
    "将类成员函数和非成员函数分组，使经常一起使用的函数在内存中位置相近，也能提高缓存性能。这是因为函数在内存中的地址取决于它们在开发者源代码中的位置，相邻的函数会被分配相近的内存地址。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 动态分配内存\n",
    "\n",
    "动态分配内存有一些适用场景，尤其是当容器的大小在编译时未知，并且在应用实例的生命周期内可能会增长或收缩时。对于非常大且会占用大量栈空间的对象，动态分配内存也很重要。如果不在关键路径上进行内存分配和释放，并且合理使用分配的内存块以避免影响缓存性能，那么动态分配内存也可以在低延迟应用中占有一席之地。\n",
    "\n",
    "动态分配内存的一个缺点是，分配和释放内存块的过程非常缓慢。反复分配和释放大小不一的内存块会导致堆碎片化，即会产生不同大小的空闲内存块，这些空闲块与已分配的内存块交错分布。\n",
    "\n",
    "碎片化的堆会使分配和释放过程变得更慢。除非开发者格外注意，否则已分配的内存块可能无法达到最佳对齐状态。通过指针访问动态分配的内存会导致指针别名问题，进而阻碍编译器进行优化，这一点我们之前已经了解过。动态分配内存还有其他缺点，但对于低延迟应用来说，这些是最主要的问题。因此，在低延迟应用中，最好完全避免使用动态分配内存，或者至少谨慎、少量地使用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 多线程\n",
    "\n",
    "如果低延迟应用使用多线程，那么线程以及线程之间的交互设计必须谨慎。启动和停止线程需要花费时间，所以最好避免在需要时才启动新线程，而是使用工作线程池。任务切换或上下文切换是指一个线程暂停或阻塞，另一个线程取而代之开始执行。上下文切换的成本非常高，因为这需要操作系统保存当前线程的状态，加载下一个线程的状态，然后开始处理等等，并且通常伴随着内存读写、缓存未命中、指令流水线停顿等问题。\n",
    "\n",
    "线程之间使用锁和互斥量进行同步的成本也很高，这涉及到围绕并发访问的额外检查和上下文切换开销。当多个线程访问共享资源时，需要使用`volatile`关键字，这也会阻止编译器进行一些优化。此外，不同线程可能会竞争相同的缓存行，使彼此的缓存失效，这种竞争会导致缓存性能极差。每个线程都有自己的栈，所以最好将共享数据保持在最少，并在线程的栈上局部分配变量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 最大化C++编译器优化参数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在本节的最后部分，我们将了解现代C++编译器在优化开发者编写的C++代码方面有多么强大和出色。我们将了解编译器在编译、链接和优化阶段是如何优化C++代码，以生成尽可能高效的机器代码的。我们会了解编译器是如何优化高级C++代码的，以及在哪些情况下它们未能做到最佳优化。接下来，我们将讨论应用开发者可以采取哪些措施来辅助编译器完成优化任务。最后，我们将通过具体研究GNU编译器（GCC），来了解现代C++编译器提供的不同选项。让我们从理解编译器如何优化我们的C++程序开始。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 理解编译器如何优化\n",
    "\n",
    "在本小节中，我们将了解编译器在对高级C++代码进行多次处理时采用的不同优化技术。编译器通常首先进行局部优化，然后尝试对这些较小的代码段进行全局优化。它在预处理、编译、链接和优化阶段，会对转换后的机器代码进行多次处理。大致来说，大多数编译器优化技术都有一些共同的主题，其中一些相互重叠，一些则相互冲突，下面我们就来看看这些情况。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 优化常见情况\n",
    "\n",
    "这个概念也适用于软件开发，它有助于编译器更好地优化代码。如果编译器能够了解程序执行时大部分时间会花费在哪些代码路径上，那么即使这会使很少执行的路径变慢，它也可以对常见路径进行优化以提高速度。这样总体上可以获得更好的性能，但通常编译器在编译时很难做到这一点，因为除非开发者添加指令进行指定，否则并不明确哪些代码路径更有可能被执行。我们将讨论开发者可以向编译器提供哪些提示，以帮助指定运行时哪些代码路径更有可能被执行。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 最小化分支"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现代处理器通常会在需要之前预取数据和指令，以便能够尽快执行指令。然而，当存在跳转和分支（条件分支和无条件分支）时，处理器无法100%确定提前知道需要哪些指令和数据。这意味着有时处理器会错误地预测所执行的分支，因此预取的指令和数据是错误的。发生这种情况时，会额外产生一些开销，因为现在处理器必须删除错误获取的指令和数据，用正确的指令和数据替换它们，然后再执行。循环展开、内联和分支预测提示等技术有助于减少分支和分支预测错误，从而提高性能。在本节后面部分，我们将更详细地探讨这些概念。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在很多情况下，开发者可以通过重构代码来避免分支，同时实现相同的行为。有时，这些优化机会只有开发者才能发现，因为开发者比编译器更深入地理解代码和代码行为。<br/>接下来展示一个非常简单的示例，说明如何转换使用分支的代码块，使其避免分支。这里我们使用一个枚举来跟踪执行的方向，跟踪最后买入/卖出的数量，并以两种不同的方式更新头寸。第一种方式在`fill_side`变量上使用分支，第二种方式通过假设`fill_side`变量只能取`BUY`/`SELL`值，并将其转换为整数作为数组索引，从而避免了分支。这段代码可以在[`Chapter3/branch.cpp`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/branch.cpp)文件中找到：\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用分支和不使用分支的两种实现方式计算出的结果是相同的："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fill_side:SELL fill_qty:10.\n",
      "With branching - position:-10 last-buy:0 last-sell:10.\n",
      "Without branching - position:-10 last-buy:0 last-sell:10.\n"
     ]
    }
   ],
   "source": [
    "#include <cstdio>\n",
    "#include <cstdint>\n",
    "#include <cstdlib>\n",
    "\n",
    "enum class Side : int16_t { BUY = 1, SELL = -1 };\n",
    "\n",
    "{\n",
    "  const auto fill_side = (rand() % 2 ? Side::BUY : Side::SELL);\n",
    "  const int fill_qty = 10;\n",
    "  printf(\"fill_side:%s fill_qty:%d.\\n\", (fill_side == Side::BUY ? \"BUY\" : (fill_side == Side::SELL ? \"SELL\" : \"INVALID\")), fill_qty);\n",
    "\n",
    "  { // with branching\n",
    "    int last_buy_qty = 0, last_sell_qty = 0, position = 0;\n",
    "\n",
    "    if (fill_side == Side::BUY) { position += fill_qty; last_buy_qty = fill_qty;\n",
    "    } else if (fill_side == Side::SELL) { position -= fill_qty; last_sell_qty = fill_qty; }\n",
    "\n",
    "    printf(\"With branching - position:%d last-buy:%d last-sell:%d.\\n\", position, last_buy_qty, last_sell_qty);\n",
    "  }\n",
    "\n",
    "  { // without branching\n",
    "    int last_qty[3] = {0, 0, 0}, position = 0;\n",
    "\n",
    "    auto sideToInt = [](Side side) noexcept { return static_cast<int16_t>(side); };\n",
    "\n",
    "    const auto int_fill_side = sideToInt(fill_side);\n",
    "    position += int_fill_side * fill_qty;\n",
    "    last_qty[int_fill_side + 1] = fill_qty;\n",
    "\n",
    "    printf(\"Without branching - position:%d last-buy:%d last-sell:%d.\\n\", position, last_qty[sideToInt(Side::BUY) + 1], last_qty[sideToInt(Side::SELL) + 1]);\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 重新排序和调度指令\n",
    "\n",
    "编译器可以利用先进的处理器特性，通过重新排序指令，使指令、内存和线程层面都能进行并行处理。编译器可以检测代码块之间的依赖关系，并对它们重新排序，这样程序仍然能够正确运行，但通过在处理器层面并行执行指令和处理数据，执行速度会更快。即使编译器不进行处理，现代处理器也可以重新排序指令，但如果编译器能让处理器更易于进行这项操作，也会有所帮助。这里的主要目标是通过选择和排序指令来避免现代多流水线处理器出现停顿和空闲周期，同时保持原始的逻辑流程。\n",
    "\n",
    "这里展示一个简单示例，说明如何对表达式重新排序以利用并行性。请注意，这在一定程度上是假设性的，因为实际实现会因处理器和编译器的不同而有很大差异："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "x = a + b + c + d + e + f;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "按照原样编写，这个表达式存在数据依赖，会大致按顺序执行，如下所示，需要5个时钟周期："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "x = a + b;\n",
    "x = x + c;\n",
    "x = x + d;\n",
    "x = x + e;\n",
    "x = x + f;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "它可以重新排序为以下指令，假设先进的处理器一次可以执行两个加法操作，这样就可以减少到3个时钟周期。这是因为像`x = a + b;`和`p = c +d;`这样的两个操作是相互独立的，可以并行执行："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "x = a + b; p = c + d;\n",
    "q = e + f; x = x + p;\n",
    "x = x + q;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 根据架构使用特殊指令\n",
    "\n",
    "在编译过程中，编译器可以选择使用哪些CPU指令来实现高级程序逻辑。当编译器为特定架构生成可执行文件时，它可以使用该架构支持的特殊指令。这意味着有机会生成更高效的指令序列，充分利用架构提供的特殊指令。我们将在“了解编译器优化标志”部分介绍如何指定这一点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 向量化（Vectorization）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现代处理器可以使用向量寄存器对多个数据并行执行多个计算。例如，SSE2指令集有128位向量寄存器，根据数据类型的大小，可用于对多个整数或浮点数执行多种操作。进一步扩展，比如AVX2指令集有256位向量寄存器，能支持更高程度的向量化操作。从技术上讲，这种优化可视为之前 “根据架构使用特殊指令” 部分讨论的内容。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了更好地理解向量化，我们来看下面这个非常简单的示例，该示例通过一个循环对两个数组进行操作，并将结果存储在另一个数组中（代码位于GitHub上第3章的[`vector.cpp`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/vector.cpp)）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <cstddef>\n",
    "\n",
    "const size_t size = 1024;\n",
    "[[maybe_unused]] float x[size], a[size], b[size];\n",
    "\n",
    "// no vectorization\n",
    "for (size_t i = 0; i < size; ++i) {\n",
    "  x[i] = a[i] + b[i];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于支持特殊向量寄存器（如我们之前讨论的SSE2指令集）的架构，它可以同时存储4个4字节的浮点数，并一次执行4次加法运算。在这种情况下，编译器可以利用向量化优化技术，并通过循环展开（loop unrolling）将上述代码重写为使用SSE2指令集的形式："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// vectorization\n",
    "for (size_t i = 0; i < size; i += 4) {\n",
    "  x[i] = a[i] + b[i];\n",
    "  x[i + 1] = a[i + 1] + b[i + 1];\n",
    "  x[i + 2] = a[i + 2] + b[i + 2];\n",
    "  x[i + 3] = a[i + 3] + b[i + 3];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 强度削弱（Strength reduction）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "强度削弱是一种编译器优化技术，指的是用更简单、成本更低的指令替换那些运算成本较高的复杂操作，以此提升性能。一个经典的例子是编译器用某个值的倒数相乘来替代除法运算。另一个例子是用加法运算替代循环索引的乘法运算。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们来看一个最简单的例子，这里我们尝试将价格从双精度表示法转换为整数表示法，方法是将浮点数除以最小有效价格增量。展示编译器进行强度削弱的变体是用简单的乘法替代除法。注意，`inv_min_price_increment = 1 / min_price_increment;`是一个`constexpr`表达式，所以它不会在运行时求值。这段代码位于[`Chapter3/strength.cpp`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/strength.cpp)文件中：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <cstdint>\n",
    "\n",
    "{\n",
    "  const auto price = 10.125; // prices are like: 10.125, 10.130, 10.135...\n",
    "  constexpr auto min_price_increment = 0.005;\n",
    "  [[maybe_unused]] int64_t int_price = 0;\n",
    "\n",
    "  // no strength reduction\n",
    "  int_price = price / min_price_increment;\n",
    "\n",
    "  // strength reduction\n",
    "  constexpr auto inv_min_price_increment = 1 / min_price_increment;\n",
    "  int_price = price * inv_min_price_increment;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 内联（Inlining）\n",
    "\n",
    "正如我们之前了解到的，函数调用的开销较大。这一过程包含多个步骤：\n",
    "\n",
    "- 保存变量和当前执行状态。\n",
    "- 从被调用函数加载变量和指令。\n",
    "- 执行这些指令，可能返回值，并在函数调用后恢复执行。\n",
    "\n",
    "编译器会尽可能用函数体替换函数调用，以此消除函数调用带来的开销，优化性能。不仅如此，由于编译器用实际函数体替换了函数调用，这为更多优化创造了空间，因为编译器可以检查这个更大的代码块。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 常量折叠（Constant folding）和常量传播（Constant propagation）\n",
    "\n",
    "常量折叠是一种显而易见的优化技术，当表达式的输出完全可以在编译时计算，且不依赖运行时分支或变量时，就可以应用该技术。然后，编译器会在编译时计算这些表达式，并用编译时常量输出值替换表达式的求值过程。\n",
    "\n",
    "一种与之相似且紧密相关的编译器优化技术是跟踪代码中已知的编译时常量值，并尝试传播这些常量值，从而挖掘更多优化机会。这种优化技术被称为常量传播。例如，如果编译器能够确定循环迭代器的起始值、增量值或终止值，就可以进行循环展开。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 死代码消除（Dead Code Elimination，DCE）\n",
    "\n",
    "当编译器检测到对程序行为没有影响的代码块时，就会应用死代码消除技术。这可能是因为这些代码块永远不会被用到，或者其中的计算结果最终没有被使用，也不会影响程序的最终输出。一旦编译器检测到这样的死代码块，就可以将其删除，从而提高程序性能。现代编译器在检测到某些代码的运行结果未被使用时，会发出警告，帮助开发者发现这类情况。不过，编译器无法在编译时检测到所有这类情况，在代码转换为机器码指令后，仍然存在进行死代码消除的机会。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 公共子表达式消除（Common Subexpression Elimination，CSE）\n",
    "\n",
    "公共子表达式消除是一种特定的优化技术，编译器通过查找重复的指令集或计算过程，重构代码，只计算一次结果，然后在需要的地方使用该值，以此消除冗余。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 窥孔优化（Peephole optimizations）\n",
    "\n",
    "窥孔优化是一个相对通用的编译器优化术语，指的是编译器在短指令序列中寻找局部优化的技术。我们使用 “局部” 这个词，是因为编译器并不一定需要理解整个程序并进行全局优化。当然，通过反复迭代地进行窥孔优化，编译器可以在全局范围内实现一定程度的优化。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 尾调用优化（Tail call optimization）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们知道，函数调用成本不低，因为传递参数和返回结果会带来开销，还会影响缓存性能和处理器流水线。尾调用优化是指编译器将递归函数调用替换为循环的优化技术。这具有明显的性能优势，比如消除函数调用开销和栈操作，还能避免可能的栈溢出情况。<br/>下面是一个简单的递归阶乘实现示例。目前，你可以忽略`[[maybe_unused]]`和`attribute ((noinline))`属性，`attribute ((noinline))`用于明确防止编译器将`factorial()`函数直接内联到`main()`函数中。该示例位于GitHub上[`Chapter3/tail_call.cpp`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/tail_call.cpp)源文件中："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// https://godbolt.org/z/EGsfW99ob\n",
    "// https://godbolt.org/z/M7fP9KhM1\n",
    "\n",
    "auto __attribute__ ((noinline)) factorial(unsigned n) -> unsigned {\n",
    "  return (n ? n * factorial(n - 1) : 1);\n",
    "}\n",
    "\n",
    "{\n",
    "  [[maybe_unused]] volatile auto res = factorial(100);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于这个实现，我们原本预期在`factorial()`函数的机器码中会看到对其自身的调用，但在开启优化进行编译时，编译器会执行尾调用优化，将`factorial()`函数实现为一个循环，而非递归。要查看机器码，可以使用类似如下命令编译这段代码："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! g++ -S -Wall -O3 tail_call.cpp ; cat tail_call.s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在`tail_call.s`文件中，你会看到`main()`函数中对`factorial()`的调用类似以下示例。如果你是第一次查看汇编代码，下面快速介绍一下你会遇到的指令：\n",
    "\n",
    "- `movl`指令将一个值移动到寄存器中（在以下代码块中是100）。\n",
    "- `call`指令调用一个函数（`factorial()`，带有名称修饰，即C++编译器在中间代码中修改函数名的步骤，参数通过`edi`寄存器传递）。\n",
    "- `testl`指令比较两个寄存器，如果相等则设置零标志位。\n",
    "- `je`和`jne`指令检查零标志位是否设置，如果设置则跳转到指定内存地址（`je`），否则跳转到指定内存地址（`jne`）。\n",
    "- `ret`指令从函数返回，返回值存储在`eax`寄存器中："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "main:\n",
    ".LFB1\n",
    "movl $100, %edi\n",
    "call _Z9factorialj"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当查看`factorial()`函数本身时，你会发现一个循环（`je`和`jne`指令），而不是对自身的额外调用指令："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "_Z9factorialj:\n",
    ".LFB0:\n",
    "movl\n",
    "testl\n",
    "je .L3\n",
    "imull\n",
    "subl\n",
    "jne\n",
    "ret\n",
    ".L4:\n",
    "ret\n",
    "movl $1, %eax\n",
    "%edi, %edi\n",
    ".L4\n",
    "%edi, %eax\n",
    "$1, %edi\n",
    ".L3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 循环展开（Loop unrolling）\n",
    "\n",
    "循环展开是将循环体复制多次。有时，编译器在编译时无法确定循环的执行次数，在这种情况下，它会部分展开循环。对于循环体较小，和 / 或可以确定循环执行次数较少的循环，编译器可以完全展开循环。这样可以避免检查循环计数器的需求，以及条件分支或循环带来的开销。这就像函数内联，将函数调用替换为函数体；对于循环展开，则是将整个循环展开，替换条件循环体。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 额外的循环优化\n",
    "\n",
    "循环展开是编译器采用的主要循环相关优化技术，但还有其他的循环优化方法：\n",
    "\n",
    "- 循环裂变（Loop fission）将一个循环分解为多个对较小数据集进行操作的循环，以提高缓存引用的局部性。\n",
    "- 循环融合（Loop fusion）则相反，如果两个相邻循环执行次数相同，可以将它们合并为一个，以减少循环开销。\n",
    "- 循环倒置（Loop inversion）是一种将`while`循环转换为`if`条件语句内部的`do-while`循环的技术。这样在循环执行时，跳转总数会减少两次，通常适用于预计至少会执行一次的循环。\n",
    "- 循环交换（Loop interchange）会交换内循环和外循环，尤其是在这样做能提高缓存引用局部性的情况下——例如，在遍历数组时，连续访问内存会对性能产生巨大影响。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 寄存器变量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "寄存器是处理器的内部存储器，由于离处理器最近，它是处理器可使用的最快存储形式。因此，编译器会尝试将访问次数最多的变量存储在寄存器中。然而，寄存器的数量有限，所以编译器需要有效地选择要存储的变量，而这种选择的有效性会对性能产生显著影响。编译器通常会选择局部变量、循环计数器和迭代器变量、函数参数、常用表达式或归纳变量（在每次循环迭代中按固定数量变化的变量）等变量。编译器能放入寄存器的变量存在一些限制，比如那些需要通过指针获取地址的变量，或者需要驻留在主内存中的引用变量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在，我们来看一个简单的例子，展示编译器如何使用归纳变量转换循环表达式。见下面的代码（可在GitHub上的[`Chapter3/induction.cpp`](https://github.com/PacktPublishing/Building-Low-Latency-Applications-with-CPP/blob/main/Chapter3/induction.cpp)中查看）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "int main() {\n",
    "  [[maybe_unused]] int a[100];\n",
    "\n",
    "  // original\n",
    "  for(auto i = 0; i < 100; ++i)\n",
    "    a[i] = i * 10 + 12;\n",
    "\n",
    "  // 这段代码会被转换为类似下面的形式，避免在循环中进行乘法运算，而是用基于归纳变量的加法来替代：\n",
    "\n",
    "  // optimized\n",
    "  int temp = 12;\n",
    "  for(auto i = 0; i < 100; ++i) {\n",
    "    a[i] = temp;\n",
    "    temp += 10;\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 活跃范围分析\n",
    "\n",
    "活跃范围（Live range）这个术语描述了变量处于活动状态或被使用的代码块。如果同一代码块中有多个变量的活跃范围重叠，那么每个变量都需要不同的存储位置。然而，如果变量的活跃范围不重叠，编译器就可以在每个活跃范围内为多个变量使用相同的寄存器。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 重计算（Rematerialization）\n",
    "\n",
    "重计算是一种编译器技术，编译器会选择重新计算一个值（假设计算很简单），而不是访问已经包含该计算结果的内存位置。这种重新计算的输出值必须存储在寄存器中，所以这项技术要与寄存器分配技术配合使用。其主要目的是避免访问缓存和主内存，因为访问它们比访问寄存器存储要慢。当然，这取决于确保重新计算所花费的时间比访问缓存或内存的时间少。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 代数化简"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "编译器可以找出能够使用代数法则进一步化简和简化的表达式。虽然软件开发人员不会故意把表达式复杂化，但在某些情况下，与开发人员最初在C++中编写的表达式相比，存在更简单的形式。由于内联、宏展开、常量合并等操作，编译器在迭代优化代码时，也会出现代数化简的机会。\n",
    "\n",
    "这里需要注意的是，编译器通常不会对浮点运算应用代数化简，因为在C++中，由于精度问题，浮点运算的化简并不安全。需要打开特定标志才能强制编译器进行不安全的浮点代数化简，但开发人员最好自己显式且正确地进行化简。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们能想到的最简单的例子是，编译器可能会将这个表达式："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "if(!a && !b) {}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "改写为使用两个操作而非之前的三个操作，如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "if(!(a || b)) {}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 归纳变量分析\n",
    "\n",
    "与归纳变量相关的编译器优化技术背后的理念是，一个与循环计数器变量呈线性函数关系的表达式，可以简化为一个在前一个值基础上进行简单加法的表达式。最简单的例子可能是计算数组中元素的地址，下一个元素的内存位置等于当前元素的位置加上对象类型的大小。这只是一个简单示例，因为在现代编译器和处理器中，有专门的指令来计算数组元素的地址，实际上并不需要使用归纳法，但基于归纳变量的优化仍然会应用于其他循环表达式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 循环不变代码外提（Loop invariant code movement）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当编译器确定循环内的某些代码和指令在整个循环期间都是常量时，就可以将该表达式移出循环。如果循环内的表达式根据分支条件有条件地产生一个值或另一个值，这些表达式也可以移出循环。此外，如果循环内每个分支都执行某些表达式，这些表达式也可以移出分支，甚至可能移出循环。有很多这样的优化可能性，但基本思想是，不需要在每次循环迭代时执行的代码，或者可以在循环前计算一次的代码，都属于循环不变代码重构的范畴。<br/>下面是一个假设的例子，展示编译器实现的循环不变代码外提是如何工作的。第一个代码块是开发人员最初编写的代码，但编译器可以识别出对`doSomething()`的调用以及涉及`b`变量的表达式是循环不变的，只需要计算一次。你可以在`Chapter3/ loop_invariant.cpp`文件中找到这段代码："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <cstdlib>\n",
    "\n",
    "{\n",
    "  auto doSomething = [](double r) noexcept { return 3.14 * r * r; };\n",
    "  [[maybe_unused]] int a[100], b = rand();\n",
    "\n",
    "  // original\n",
    "  for(auto i = 0; i < 100; ++i)\n",
    "    a[i] = (doSomething(50) + b * 2) + 1;\n",
    "\n",
    "  // loop invariant\n",
    "  auto temp = (doSomething(50) + b * 2) + 1;\n",
    "  for(auto i = 0; i < 100; ++i)\n",
    "    a[i] = temp;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 基于静态单赋值（Static Single Assignment，SSA）的优化\n",
    "\n",
    "SSA是原始程序的一种转换形式，其中指令被重新排序，使得每个变量只在一个地方被赋值。经过这种转换后，编译器可以利用每个变量只在一个地方被赋值的特性，应用许多额外的优化。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 去虚拟化（Devirtualization）\n",
    "\n",
    "去虚拟化是一种编译器优化技术，尤其适用于C++，旨在调用虚函数时避免**虚表（Virtual Table，vtable）**查找。这种优化技术归结为编译器在编译时确定要调用的正确方法。即使使用虚函数，这种情况也可能发生，比如在某些情况下，对象类型在编译时是已知的，例如当纯虚函数只有一个实现时。\n",
    "\n",
    "另一种情况是，编译器可以确定在某些上下文或代码分支中只创建和使用了一个派生类，那么它可以将使用虚表的间接函数调用替换为对正确派生类型方法的直接调用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 理解编译器何时无法优化\n",
    "\n",
    "在本节中，我们将讨论编译器无法应用上一节所讨论的某些优化技术的不同场景。了解编译器何时无法优化，有助于我们编写避免这些问题的C++代码，以便编译器能够对代码进行高度优化，生成高效的机器代码。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 跨模块优化失败\n",
    "\n",
    "编译器在编译整个程序时，会以文件为单位逐个独立编译模块。因此，编译器除了当前正在编译的模块外，并不了解其他模块中的函数信息。这使得它无法跨模块优化函数，并且我们提到的许多技术也无法应用，因为编译器并不理解整个程序。现代编译器通过使用**链接时优化(LTO，Link-Time Optimization)**来解决这类问题。在单独的模块编译完成后，链接器会在编译时将不同模块视为同一翻译单元的一部分。这会激活我们到目前为止讨论过的所有优化，所以在优化整个应用程序时，启用LTO非常重要。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 动态内存分配\n",
    "\n",
    "我们已经知道，动态内存分配在运行时速度较慢，会给应用程序引入不确定的延迟。它还有另一个副作用，即指向这些动态分配内存块的指针会出现指针别名（pointer aliasing）问题。接下来我们会更详细地探讨指针别名问题。对于动态分配的内存块，即使在程序员看来很明显，编译器也无法确定指针必然指向不同且不重叠的内存区域。这就阻碍了各种依赖于数据对齐或假设对齐的编译器优化，以及与指针别名相关的低效问题，我们接下来会详细说明。局部存储和声明的缓存效率也更高，因为随着新函数被调用和局部对象被创建，内存空间会频繁复用。而动态分配的内存块可能会随机分散在内存中，导致缓存性能较差。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 指针别名\n",
    "\n",
    "通过指针或引用访问变量时，虽然开发人员可能很清楚哪些指针指向不同且不重叠的内存位置，但编译器却无法100%确定。换句话说，编译器无法保证某个指针没有指向代码块中的另一个变量，或者不同指针没有指向重叠的内存位置。由于编译器必须考虑这种可能性，这就阻碍了我们之前讨论的许多编译器优化，因为它们不能再安全地应用。在C++代码中有一些方法可以指定哪些指针编译器可以安全地假设不是别名。另一种方法是指示编译器在整个代码中假设不存在指针别名，但这要求开发人员分析所有指针和引用，确保永远不会出现别名，这并非易事。最后，还有一种选择是在编写代码时明确考虑这些对编译器优化的阻碍因素来进行优化，这同样不简单。\n",
    "\n",
    "关于处理指针别名问题，我们的建议如下：\n",
    "\n",
    "1. 在将指针传递给函数时，在函数声明中使用`__restrict`关键字，指示编译器对标记有该说明符的指针假设不存在指针别名。\n",
    "2. 如果需要进一步优化，我们建议明确优化代码路径，并考虑指针别名相关问题。\n",
    "3. 最后，如果仍然需要更多优化，我们可以指示编译器在整个代码库中假设不存在指针别名，但这是一个危险的选项，应仅作为最后的手段使用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 浮点归纳变量\n",
    "\n",
    "编译器通常不会对浮点表达式和变量使用归纳变量优化。这是由于我们之前讨论过的舍入误差和精度问题。这就使得在处理浮点表达式和值时，编译器无法进行优化。有一些编译器选项可以启用不安全的浮点优化，但开发人员必须确保检查每个表达式，并以一种不会因编译器优化导致精度问题产生意外副作用的方式来编写它们。这并非易事，因此开发人员应谨慎地要么显式优化浮点表达式，要么分析不安全编译器优化带来的副作用。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 虚函数和函数指针\n",
    "\n",
    "我们已经讨论过，对于虚函数和函数指针，编译器在编译时无法进行优化，因为在许多情况下，编译器无法确定运行时会调用哪个方法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 了解编译器优化标志\n",
    "\n",
    "到目前为止，我们已经讨论了编译器使用的不同优化技术，以及编译器无法优化我们C++代码的不同情况。生成优化的低延迟代码有两个基本要点。第一是编写高效的C++代码，并在编译器可能无法优化的情况下进行手动优化。第二是尽可能为编译器提供更多的可见性和信息，以便它能够做出正确且最佳的优化决策。我们可以通过用于配置编译器的编译器标志（compiler flags）来向编译器传达我们的意图。\n",
    "\n",
    "在本节中，我们将了解GCC编译器的标志，因为这是本书中使用的编译器。不过，大多数现代编译器都有类似于我们在本节中讨论的用于配置优化的标志。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 处理编译器优化标志的方法\n",
    "\n",
    "总体而言，处理GCC编译器优化标志的一般方法如下：\n",
    "\n",
    "- 通常首选最高优化级别，所以`-O3`是一个不错的起点，它启用了许多优化，我们很快就会看到这些优化。\n",
    "- 在实践中测量应用程序的性能是衡量和优化关键代码路径的最佳方法。当启用`-fprofile-generate`选项时，GCC本身可以执行基于剖析的优化（Profile-Guided Optimization，PGO）。编译器会确定程序的流程，并统计每个函数和代码分支的执行次数，以找到关键代码路径的优化方法。\n",
    "- 由于我们之前讨论过的原因，启用链接时优化（LTO）是生成最低延迟机器代码的良好实践，没有它编译器就无法跨模块优化。对于GCC，`-flto`参数为我们的应用程序启用LTO。`-fwhole-program`选项启用全程序优化（WPO，Whole-Program Optimization），将整个代码库视为一个整体程序进行过程间优化。\n",
    "- 让编译器为应用程序运行的特定架构生成构建版本是个好主意。这使编译器能够使用特定于该架构的特殊指令集，并最大化优化机会。对于GCC，可以使用`-march`参数启用此功能。\n",
    "- 建议禁用运行时类型信息（RTTI，Run-Time Type Information），因为RTTI依赖于在运行时确定对象的类型。对于GCC，可以使用`-no-rtti`参数实现这一点。\n",
    "- 可以指示GCC编译器启用快速浮点值优化，甚至启用不安全的浮点优化。GCC有`-ffp-model=fast`、`-funsafe-math-optimizations`和`-ffinite-math-only`选项来启用这些不安全的浮点优化。使用这些标志时，开发人员必须仔细考虑操作顺序以及这些操作产生的精度问题。当使用`-ffinite-math-only`这样的参数时，要确保所有浮点变量和表达式都是有限的，因为这种优化依赖于这个属性。`-fno-trapping-math`和`-fno-math-errno`允许编译器通过假设不依赖异常处理或`errno`全局变量进行错误信号传递，对包含浮点运算的循环进行向量化处理。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 理解GCC优化标志的详细信息\n",
    "\n",
    "在本节中，我们将提供有关可用的GCC优化标志的更多详细信息。可用的优化标志完整列表非常庞大，超出了本书的范围。首先，我们将描述在GCC中启用更高级别的优化指令`-O1`、`-O2`和`-O3`会启用哪些功能，我们鼓励感兴趣的读者从GCC手册中更详细地了解其中每一项。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 优化级别`-O1`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`-O1`是第一级优化，启用下表中列出的标志。在这个级别，编译器试图在不会大幅增加编译、链接和优化时间的前提下，减少代码大小和执行时间。这些是最重要的优化级别，基于我们在本章中讨论的内容，提供了巨大的优化机会。接下来我们将讨论其中一些标志。\n",
    "\n",
    "`-fdce`和`-fdse`执行死代码消除（DCE，Dead Code Elimination）和死存储消除（Dead Store Elimination，DSE）。\n",
    "\n",
    "`-fdelayed-branch`在许多架构上受支持，它试图重新排序指令，以便在延迟分支指令之后最大化流水线的吞吐量。\n",
    "\n",
    "`-fguess-branch-probability`尝试基于启发式方法猜测开发人员未提供任何提示的分支的分支概率。\n",
    "\n",
    "`-fif-conversion`和`-fif-conversion2`尝试通过使用类似于我们在本章中讨论的技巧将分支转换为无分支等效形式来消除分支。\n",
    "\n",
    "`-fmove-loop-invariants`启用循环不变代码移动优化。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果感兴趣，你应该研究这些标志的详细信息，因为讨论每个参数超出了本书的范围。\n",
    "\n",
    "| `-fauto-inc-dec`                 | `-fshrink-wrap`          |\n",
    "| :------------------------------- | :----------------------- |\n",
    "| `-fbranch-count-reg`             | `-fshrink-wrap-separate` |\n",
    "| `-fcombine-stack-adjustments`    | `-fsplit-wide-types`     |\n",
    "| `-fcompare-elim`                 | `-fssa-backprop`         |\n",
    "| `-fcprop-registers`              | `-fssa-phiopt`           |\n",
    "| `-fdce`                          | `-ftree-bit-ccp`         |\n",
    "| `-fdefer-pop`                    | `-ftree-ccp`             |\n",
    "| `-fdelayed-branch`               | `-ftree-ch`              |\n",
    "| `-fdse`                          | `-ftree-coalesce-vars`   |\n",
    "| `-fforward-propagate`            | `-ftree-copy-prop`       |\n",
    "| `-fguess-branch-probability`     | `-ftree-dce`             |\n",
    "| `-fif-conversion`                | `-ftree-dominator-opts`  |\n",
    "| `-fif-conversion2`               | `-ftree-dse`             |\n",
    "| `-finline-functions-called-once` | `-ftree-forwprop`        |\n",
    "| `-fipa-modref`                   | `-ftree-fre`             |\n",
    "| `-fipa-profile`                  | `-ftree-phiprop`         |\n",
    "| `-fipa-pure-const`               | `-ftree-pta`             |\n",
    "| `-fipa-reference`                | `-ftree-scev-cprop`      |\n",
    "| `-fipa-reference-addressable`    | `-ftree-sink`            |\n",
    "| `-fmerge-constants`              | `-ftree-slsr`            |\n",
    "| `-fmove-loop-invariants`         | `-ftree-sra`             |\n",
    "| `-fmove-loop-stores`             | `-ftree-ter`             |\n",
    "| `-fomit-frame-pointer`           | `-funit-at-a-time`       |\n",
    "| `-freorder-blocks`               |                          |\n",
    "\n",
    "表3.1：启用`-O1`时启用的GCC优化标志"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 优化级别 -O2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-O2是下一个优化级别，在这个级别，GCC会执行更多的优化，这会导致编译和链接时间变长。-O2除了启用-O1的标志外，还会添加下表中的标志。我们将简要讨论其中一些标志，感兴趣的读者可以深入探讨每个标志的详细内容。\n",
    "\n",
    "`-falign-functions`、`-falign-labels`和`-falign-loops`用于对齐函数的起始地址、跳转目标和循环位置，以便处理器能够尽可能高效地访问它们。我们在本章中讨论的最优数据对齐原则同样适用于指令地址。\n",
    "\n",
    "`-fdelete-null-pointer-checks`让程序假设解引用空指针是不安全的，并利用这个假设进行常量折叠、消除空指针检查等操作。\n",
    "\n",
    "`-fdevirtualize`和`-fdevirtualize-speculatively`会尽可能将虚函数调用转换为直接函数调用。这反过来又可能因为内联而带来更多优化。\n",
    "\n",
    "`-fgcse`启用全局公共子表达式消除（Global Common Subexpression Elimination，GCSE）和常量传播。\n",
    "\n",
    "`-finline-functions`、`-finline-functions-called-once`和`-findirect-inlining`提高了编译器内联函数的积极性，并寻找由于之前的优化过程而产生的间接内联机会。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| `-falign-functions -falign-jumps`               | `-foptimize-sibling-calls`                           |\n",
    "| :---------------------------------------------- | :--------------------------------------------------- |\n",
    "| `-falign-labels -falign-loops`                  | `-foptimize-strlen`                                  |\n",
    "| `-fcaller-saves`                                | `-fpartial-inlining`                                 |\n",
    "| `-fcode-hoisting`                               | `-fpeephole2`                                        |\n",
    "| `-fcrossjumping`                                | `-freorder-blocks-algorithm=stc`                     |\n",
    "| `-fcse-follow-jumps -fcse-skip-blocks`          | `-freorder-blocks-and-partition -freorder-functions` |\n",
    "| `-fdelete-null-pointer-checks`                  | `-frerun-cse-after-loop`                             |\n",
    "| `-fdevirtualize -fdevirtualize-speculatively`   | `-fschedule-insns -fschedule-insns2`                 |\n",
    "| `-fexpensive-optimizations`                     | `-fsched-interblock -fsched-spec`                    |\n",
    "| `-ffinite-loops`                                | `-fstore-merging`                                    |\n",
    "| `-fgcse -fgcse-lm`                              | `-fstrict-aliasing`                                  |\n",
    "| `-fhoist-adjacent-loads`                        | `-fthread-jumps`                                     |\n",
    "| `-finline-functions`                            | `-ftree-builtin-call-dce`                            |\n",
    "| `-finline-small-functions`                      | `-ftree-loop-vectorize`                              |\n",
    "| `-findirect-inlining`                           | `-ftree-pre`                                         |\n",
    "| `-fipa-bit-cp -fipa-cp -fipa-icf`               | `-ftree-slp-vectorize`                               |\n",
    "| `-fipa-ra -fipa-sra -fipa-vrp`                  | `-ftree-switch-conversion -ftree-tail-merge`         |\n",
    "| `-fisolate-erroneous-paths-dereference`         | `-ftree-vrp`                                         |\n",
    "| `-flra-remat`                                   | `-fvect-cost-model=very-cheap`                       |\n",
    "\n",
    "表3.2 -O2启用时除-O1标志外额外启用的GCC优化标志"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 优化级别 -O3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-O3是GCC中最激进的优化选项，只要程序性能更好，即使会导致可执行文件变大，它也会进行优化。-O3除了启用-O2的标志外，还会启用下表中的标志。我们先简要讨论几个重要的标志，然后给出完整列表。\n",
    "\n",
    "`-fipa-cp-clone`创建函数克隆，通过牺牲可执行文件大小来提高执行速度，从而使过程间常量传播和其他形式的优化更有效。\n",
    "\n",
    "`-fsplit-loops`尝试在循环中，如果可以通过将循环分成两部分来避免分支（例如，在交易算法的循环中，根据条件检查执行不同代码块的情况），就对循环进行拆分。\n",
    "\n",
    "`-funswitch-loops`将循环不变的分支移出循环，以最小化分支。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| `-fgcse-after-reload`                           | `-fsplit-paths`               |\n",
    "| :---------------------------------------------- | :---------------------------- |\n",
    "| `-fipa-cp-clone -floop-interchange`             | `-ftree-loop-distribution`    |\n",
    "| `-floop-unroll-and-jam`                         | `-ftree-partial-pre`          |\n",
    "| `-fpeel-loops`                                  | `-funswitch-loops`            |\n",
    "| `-fpredictive-commoning`                        | `-fvect-cost-model=dynamic`   |\n",
    "| `-fsplit-loops`                                 | `-fversion-loops-for-strides` |\n",
    "\n",
    "表3.3 -O3启用时除-O2标志外额外启用的GCC优化标志"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们将讨论一些在优化低延迟应用时很有用的其他编译器优化标志。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 静态链接\n",
    "\n",
    "`-l library`选项传递给链接器，用于指定将可执行文件与哪个库链接。但是，如果链接器同时找到名为`liblibrary.a`的静态库和名为`liblibrary.so`的共享库，那么我们必须指定`-static`参数，以防止链接共享库，转而选择静态库。我们之前讨论过为什么对于低延迟应用来说，静态链接比共享库链接更受青睐。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 目标架构\n",
    "\n",
    "`-march`参数用于指定编译器构建最终可执行二进制文件的目标架构。例如，`-march=native`指定编译器为其正在构建的架构构建可执行文件。我们在此重申，当编译器知道应用程序的目标运行架构时，它可以利用该架构的相关信息（如扩展指令集等）来提高优化效果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 警告\n",
    "\n",
    "`-Wall`、`-Wextra`和`-Wpendantic`参数用于控制编译器在检测到各种不同情况（这些情况在技术上不是错误，但可能不安全）时生成的警告数量。对于大多数应用程序，建议启用这些参数，因为它们可以检测开发者代码中的潜在错误和拼写错误。虽然这些参数不会直接影响编译器优化应用程序的能力，但有时警告会促使开发者检查代码中的歧义或次优情况，例如意外或隐式的类型转换，这些可能会导致效率低下。`-Werror`参数会将这些警告转换为错误，强制开发者在编译成功之前检查并修复每个产生编译器警告的情况。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 不安全的快速数学运算\n",
    "\n",
    "在没有充分考虑和尽职调查的情况下，不应启用这一类编译器优化标志。在C++中，编译器不能应用许多依赖于浮点运算产生有效值、浮点表达式具有结合性等属性的浮点优化。回顾一下，这是因为硬件中浮点值的表示方式，很多这类优化可能会导致精度损失和不同（甚至可能错误）的结果。启用`-ffast-math`参数会依次启用以下参数：\n",
    "\n",
    "- `-fno-math-errno`\n",
    "- `-funsafe-math-optimizations`\n",
    "- `-ffinite-math-only`\n",
    "- `-fno-rounding-math`\n",
    "- `-fno-signaling-nans`\n",
    "- `-fcx-limited-range`\n",
    "- `-fexcess-precision=fast`\n",
    "\n",
    "这些参数允许编译器对浮点表达式进行优化，即使这些优化是不安全的。在上述三个优化级别中，这些参数都不会自动启用，因为它们不安全，只有在开发者确信不会因这些参数而出现错误或副作用时才应启用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 总结\n",
    "\n",
    "在本章中，我们首先讨论了适用于任何编程语言开发低延迟应用的通用建议。我们探讨了开发这类应用时理想的软件工程方法，以及如何思考、设计、开发和评估数据结构和算法等构建模块的使用。\n",
    "\n",
    "我们强调，对于低延迟应用开发来说，对处理器架构、缓存和内存布局与访问、C++编程语言的底层工作原理以及编译器如何优化代码等方面的了解程度，将决定开发的成败。测量和提高性能也是低延迟应用的关键组成部分，我们将在本书结尾深入探讨这些细节。\n",
    "\n",
    "我们花了大量时间讨论不同的C++原理、结构和特性，目的是了解它们在底层的实现方式。这里的目标是摒弃次优的编程实践，并强调在低延迟应用开发中使用C++的一些理想方面。\n",
    "\n",
    "在本书的其余部分，当我们构建低延迟电子交易生态系统（相互交互的应用程序集合）时，我们将在避免某些C++特性而使用其他特性的过程中，强化和拓展我们在这里讨论的这些理念。\n",
    "\n",
    "在本章的最后一节，我们详细讨论了C++编译器的许多方面。我们试图让大家了解编译器如何优化开发者的高级代码，即它们可以采用哪些技术。我们还研究了编译器无法优化开发者代码的情况。目的是让你明白如何在输出尽可能最优的机器代码时利用编译器的优势，并帮助编译器避免出现无法优化的情况。最后，我们介绍了GNU GCC编译器可用的不同优化标志，本书后续部分将使用该编译器。\n",
    "\n",
    "在下一章中，我们将把理论知识付诸实践，开始用C++实现低延迟应用的一些常见构建模块。我们的目标是构建低延迟且高性能的组件。我们将仔细运用本章讨论的原则和技术来构建这些高性能组件。在后面的章节中，我们将使用这些组件来构建电子交易生态系统。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
